package solution;

import solution.util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * <a href="https://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83?tpId=117&&tqId=37715&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking">
 * NC5 二叉树根节点到叶子节点的所有路径和</a>
 *
 * @author or2
 * @Description 给定一个仅包含数字\ 0-9 0−9 的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。
 * 例如根节点到叶子节点的一条路径是1\to 2\to 31→2→3,那么这条路径就用\ 123 123 来代替。
 * 找出根节点到叶子节点的所有路径表示的数字之和
 * @create 2021年09月08日 时间: 9:25
 */
public class SumNumbers {
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int sumNumbers (TreeNode root) {
//        答案暂存变量
        int ans = 0;
//        深度遍历暂存遍历
        LinkedList<Integer> dfsAux = new LinkedList<>();
//        每次深度到底的和
        ArrayList<Integer> ansToSum = new ArrayList<>();

        dfs(root, dfsAux, ansToSum);

        for (Integer integer : ansToSum) {
            ans += integer;
        }
        return ans;
    }

    /**
     * 深度遍历
     * @param curNode 当前结点
     * @param auxArr 当前路径
     * @param ansToSum 保存答案
     */
    private void dfs(TreeNode curNode, LinkedList<Integer> auxArr, ArrayList<Integer> ansToSum) {
        if (curNode == null) {
            return;
        }
        auxArr.add(curNode.val);
//        终止条件(当前结点为叶子节点)
        if (curNode.left == null && curNode.right == null) {
            StringBuilder strBuilder = new StringBuilder();
            for (Integer integer : auxArr) {
                strBuilder.append(integer);
            }
            ansToSum.add(Integer.valueOf(strBuilder.toString()));
            return;
        }

        if (curNode.left != null) {
            dfs(curNode.left, auxArr, ansToSum);
//            回溯, 还原当前路径信息
            auxArr.removeLast();
        }
        if (curNode.right != null) {
            dfs(curNode.right, auxArr, ansToSum);
//            回溯, 还原当前路径信息
            auxArr.removeLast();
        }

    }
}
